package com.lw.leetcode.binary.b;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * stack
 * 题目-02. 销售出色区间
 *
 * @author liw
 * @version 1.0
 * @date 2022/9/26 9:40
 */
public class LongestESR {

    public static void main(String[] args) {
        LongestESR test = new LongestESR();

        // 5
//        int[] arr = {10, 2, 1, 4, 3, 9, 6, 9, 9};

        // 5
//        int[] arr = {3, 7, 15, 0, 15, 6, 7, 6, 12, 3};

        int[] arr = Utils.getArr(10000, 0, 16);

        // 0
//        int[] arr = {5, 6, 7};

        int i = test.longestESR(arr);
        System.out.println(i);
    }

    private int[] counts1;

    public int longestESR(int[] sales) {
        int length = sales.length;
        int item = 0;
        int max = 0;
        int index = 1;
        counts1 = new int[length + 1];
        int[] counts2 = new int[length + 1];
        counts2[0] = -1;
        for (int i = 0; i < length; i++) {
            item += sales[i] > 8 ? 1 : -1;
            if (item > 0) {
                max = i + 1;
                continue;
            }
            if (counts1[index - 1] > item) {
                counts2[index] = i;
                counts1[index++] = item;
                continue;
            }
            if (counts1[index - 1] == item ) {
                continue;
            }
            max = Math.max(max, i - counts2[find(item, index - 1)]);

        }
        return max;
    }

    private int find(int t, int end) {
        int st = 0;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (counts1[m] < t) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return st;
    }

}
